There are many different types of packet switching network devices. One type receives network packets on one of a plurality of input ports, and then for each packet performs a lookup to determine a policy specific for the flow to which the packet belongs. This policy includes an indication of one of a plurality of output ports. The lookup process is generally referred to here as the “flow cache” or it is said that the “flow cache” program or process performs the lookup. After the lookup, the packet is sent out of the network device on the indicated output port. A switch is an example of such a network device. A router is another example of such a network device. Several such network devices have been made using a particular Island-Based Network Flow Processor (IB-NFP) integrated circuit of the NFP-6XXX family of IB-NFPs available from Netronome Systems, Inc. of Santa Clara, Calif. This prior art integrated circuit is described in U.S. Pat. No. 9,146,920.
In a first type of prior art network device that employed the NFP-6XXX IB-NFP integrated circuit, the flow cache operated as set forth in U.S. Pat. No. 8,908,693. In one implementation, the policies for packet flows and the provisioning and setup of the flow cache was carried out statically before system operation. Flow policies and lookup entries were not added or deleted dynamically as the flow cache was operating in handling the switching of packets. In a second type of prior art network device that employed the NFP-6XXX IB-NFP integrated circuit, the flow cache involved use of cache lines that stored keys. Some cache lines were cached on the IB-NFP integrated circuit in a Dcache cache memory whereas other cache lines were stored outside the IB-NFP in a bulk memory. From the incoming packet, an incoming key was determined. From the incoming key a pair of hash values was determined. The first hash value was used to read a cache line from the Dcache memory. The second hash value was then compared against one or more entries that may have been stored in the cache line. If there was a detected match between the second hash value and an entry value stored in the cache line, the result was a looked up key. The incoming key was then compared to the looked up key to determine if there was a key match. A key match pointed to a policy. This identified policy was then be used to determine how to process the packet and how to output the packet from the network device. Hash collisions where multiple input keys hashed to the same second hash value were handled by loading multiple identical second hash value entries into the cache line, one for each of these different input keys. In a third type of prior art approach, the lookup performed on the cache line does not directly return a key, but rather it returns a pointer to a data structure or to a linked list. After the lookup in the cache line, a processor read of the cache line content is performed in order to obtain the pointer from another part of the cache line. The data structure or the linked list pointed to by this pointer stores a key/keys that is/are to be compared to the incoming key. The cache line entry associated with the data structure or the linked list can be locked. See U.S. Pat. No. 9,146,920 for disclosure of how such a data structure or linked list can be locked.
The NFP-6XXX IB-NFP integrated circuit that was used or was usable in implementing these multiple different prior art approaches had a transactional memory. The transactional memory in turn included a bus interface, an atomic lookup engine and a cache memory for storing cache lines. The atomic lookup engine was capable of reading cache lines from the Dcache memory, and then performing any one of multiple different types of lookup operations on the cache line information. One of these lookup operations was the CAM128_lookup24_add_inc. Another lookup operation that the lookup engine could perform was the ALAL (Atomic Look-up, Add and Lock) CAM_lookup_add_lock operation. These lookup operations are set forth on page 160 of the document: Netronome Network Flow Processor 6xxx, NFP SDK version5.0, Flow Processor Core Programmer's Reference Manual—PRELIMINAY DRAFT (2014). For additional information on the structure of the atomic lookup engine and its associated Dcache cache memory, see: U.S. Pat. No. 9,146,920.